An Ordered Binary Decision Diagram (BDD) is a graph representation of a Boolean function. According to its good properties, BDD's are widely used in various applications. In this paper, we investigate the computational complexity of basic operations on BDD's. We consider two important operations: reduction of a BDD and binary Boolean operations based on BDD's. This paper shows that both the reduction of a BDD and the binary Boolean operations based on BDD's are NC1-reducible to REACHABILITY. That is, both of the problems belong to NC2. In order to extend the results to the BDD's with output inverters, we also considered the transformations between BDD's and BDD's with output inverters. We show that both of the transformations are also NC1-reducible to REACHBILITY.

Full scan design of sequential circuits results in greatly reducing the cost of their test generation. However, it introduces the extra expense of many test clocks to control and observe the values of flip-flops because of the need to shift values for the flip-flops into the scan panh. In this paper we propose a new method of generating compact test sequences for scan-based sequential circuits on the assumption that the number of shift clocks is allowed to vary for each test vector. The method is based on Boolean function manipulation using a shared binary decision diagram (SBDD). Although the test generation algorithm is basically for general sequential circuits, the computational cost is much lower for scan-based sequential circuits than for non-scanbased sequential circuits because the length of a test sequence for each fault is limited. Experimental results show that, for all the tested circuits, test sequences generated by the method require much smaller number of test clocks than compact or minimum test sets for combinational logic part of scan-based sequential circuits. The reduction rate was 48% on the average in the experiments.

Recently, there has been a lot of research on solving combinatorial problems using Binary Decision Diagrams (BDDs), which are very efficient representations of Boolean functions. We have already developed a Boolean Expression Manipulator, which calculates and reduces Boolean expressions quickly based on BDD techniques. This greatly aids our works on developing VLSI CAD systems and solving combinatorial problems. Any combinatorial problem can be described in Boolean expressions; however, arithmetic operations, such as addition, subraction, multiplication, equality and inequality, are also used for describing many practical problems. Arithmetic operations provide simple descriptions of problems in many cases. In this paper, we present an arithmetic Boolean expression manipulator (BEM-), based on BDD techniques. BEM- calculates Boolean expressions containing arithmetic operations and then displays the results in various formats. It can solve problems represented by a set of equalities and inequalities, which are dealt with using 0-1 linear programming. We show the efficient data structure based on BDD representation, algorihms for manipulating Boolean expressions with arithmetic operations, and good formats for displaying the results. Finally we present the specification of BEM- and an example of application to the 8-Queens problem. BEM- is customizable to various applicationa. It has good computation performance in terms of the total time for programming and execution. We expect BEM- to be a helpful tool in research and development on digital systems.

Manipulation of Boolean functions is one of the most important techniques for implementing of VLSI logic design systems. This paper presents a fast method for generating prime-irredundant covers from Binary Decision Diagrams (BDDs), which are efficient representation of Boolean functions. Prime-irredundant covers are forms in which each cube is a prime implicant and no cube can be eliminated. This new method generates compact cube sets from BDDs directly, in contrast to the conventional cube set reduction algorithms, which commonly manipulate redundant cube sets or truth tables. Our method is based on the idea of a recursive operator, proposed by Morreale. Morreale's algorithm is also based on cube set manipulation. We found that the algorithm can be improved and rearranged to fit BDD operations efficiently. The experimental results demonstrate that our method is efficient in terms of time and space. In practical time, we can generate cube sets consisting of more than 1,000,000 literals from multi-level logic circuits which have never previously been flattened into two-level logics. Our method is more than 10 times faster than ESPRESSO in large-scale examples. It gives quasi-minimum numbers of cubes and literals. This method should find many useful applications in logic design systems.

In this paper, a synthesizing method is proposed for the design of discrete-time cellular neural networks for binary image processing. Based on the theory of digital-logical design paradigm of threshold logic, the template parameters of the discrete-time cellular neural network for a prescribed binary image processing problem are calculated. Application examples including edge detection, connected component detection, and hole filling are given to demonstrate the merits and limitations of the proposed method. For a given realization of the parameters of the cloning template, a guideline for the selection of the offset Ic for maximum error tolerance is also considered.

In this paper we propose a new timing verification technique named coded time-symbolic simulation, CTSS. Our interest is on simulation of logic circuits consisting of gates whose delay is specified only by its minimum and maximum values. Conventional logic simulation based on min/max delay model leads to over-pessimistic results. In our new method, the cases of possible delay values of each gate are encoded by binary vectors. The circuit behavior for all the possible combinations of the delay values are simulated based on symbolic simulation by assigning Boolean variables to the binary vectors. This simulation technique can deal with logic circuits containing feedback loops as well as combinational circuits. We implemented an efficient simulator by using shared binary decision diagrams (SBDD's) as internal representation of Boolean functions. We also propose novel techniques of analyzing the results of CTSS.

Binary Decision Diagrams (BDDs) and Shared Binary Decision Diagrams (SBDDs), which are improved BDDs, are useful for implementing VLSI logic design systems. Recently, these representations, which are graph representations of Boolean functions, have become popular because of their efficiency in terms of time and space. The forms of the BDD vary with the order of the input variables though they represent the same function. The size of the graphs greatly depends on the order. The variable ordering algorithm is one of the most important issues in the application of BDDs. In this paper, we consider methods which reduce the graph size by reordering input variables on a given BDD with a certain variable order. We propose the Minimum-Width Method which gives a considerably good order in a practicable time and space. In the method, the order is determined by width of BDDs as a cost function. In addition, we show the effect of combining our method with the local search method, and also describe the improvement using the threshold. Experimental results show that our method can reduce the size of BDDs remarkably for most examples. The method needs no additional information, such as the topological information of the circuit. The results can be a measure for evaluation of other ordering methods.